Genetic Algorithm

Genetic Algorithm Class

The population is evolved by calling GeneticAlgorithm.evolve(). The specific implementation of the GA class is as follows:

public class GeneticAlgorithm {
    private final Selection selection;  //selection operator
    private final Crossover crossover;  //crossover operator
    private final Mutation mutation;    // mutation operator
    private final double crossoverRate; //crossover rate
    private final double mutationRate;  //mutation rate

    public GeneticAlgorithm(Selection selection, Crossover crossover, Mutation mutation, double crossoverRate, double mutationRate) {
        this.selection = selection;
        this.mutation = mutation;
        this.crossover = crossover;
        this.mutationRate = mutationRate;
        this.crossoverRate = crossoverRate;
    }

    public Population evolve(Population population) {
         //种群演化
        List<Chromosome> nextGeneration = new ArrayList<>();
        while (nextGeneration.size() < population.size()) {
            Chromosome c1 = selection.select(population);
            Chromosome c2 = selection.select(population);
            ChromosomePair pair = new ChromosomePair(c1, c2);
            if (randomGenerator.nextDouble() < crossoverRate) {
                pair = this.crossover.crossover(c1, c2);
            }
            Chromosome first = pair.getFirst();
            Chromosome second = pair.getSecond();
            if (randomGenerator.nextDouble() < mutationRate) {
                first = mutation.mutate(first);
            }
            if (randomGenerator.nextDouble() < mutationRate) {
                second = mutation.mutate(second);
            }
            nextGeneration.add(first);
            if (nextGeneration.size() < population.size()) {
                nextGeneration.add(second);
            }
        }
        return new Population(nextGeneration);
    }
}

Application

GeneticAlgorithm is instantiated with parameters and evolve function is called to generate a new population.

  GeneticAlgorithm ga = new GeneticAlgorithm(selection, crossover, mutation, crossoverRate, mutationRate);
  Population newPopulation = ga.evolve(population);

Chromosome class

After encoding each individual, use the encoded gene sequence to construct the individual's gene class.

public class Chromosome<T> {
    private final List<T> sequence;
    private final Integer fitness;
    public Chromosome(List<T> list, Integer fitness) {
        this.sequence = list;
        this.fitness = fitness;
    }
    
    public Chromosome(List<T> list) {
        this.sequence = list;
        this.fitness = 5;
    }
    
    public List<T> getSequence(){
        return this.sequence;
    }
    
    public Integer getFitness(){
        return fitness;
    }
}

Chromosome pair class

Gene needs two gene sequences to be carried out at the same time during the crossover process, so a Chromosome packaging class is required

@Getter
public class ChromosomePair {
    private final Chromosome first;
    private final Chromosome second;

    public ChromosomePair(Chromosome c1, Chromosome c2) {
        this.first = c1;
        this.second = c2;
    }

}

Population class

Build a population from a list of chromosomes

public class Population {

    private List<Chromosome> chromosomes;

    public Population(List<Chromosome> chromosomes) {
        this.chromosomes = chromosomes;
    }

    public int size(){
        return chromosomes.size();
    }

    public Chromosome getChromosome(int index){
        return chromosomes.get(index);
    }

    public List<Chromosome> getChromosomes(){
        return Collections.unmodifiableList(this.chromosomes);
    }
    
}